package sequence.linkedList;

public class MyLinkedList<E> implements Iterable<E> {
	private int theSize;	// Number of items in the list
	private Node<E> beginMarker; // Reference to the header node
	private Node<E> endMarker;	 // Reference to the tail node

	// Creates an empty list
	public MyLinkedList( ){
		doClear( ); 
	}
	private void doClear(){
		beginMarker = new Node<E>( null, null, null );
		endMarker = new Node<E>( null, beginMarker, null );
		beginMarker.next = endMarker;
		theSize = 0;	
	}
	// Initializes the list as an empty list
	public void clear( ) {
		doClear();
	}
	// Returns the number of items in the list
	public int size( ){
		return theSize;
	}
	// Says if the list is empty
	public boolean isEmpty( ){
		return size( ) == 0;
	}

	// Says if the given item is in the List
	public boolean contains(E item){
		Node<E> p;
		p = beginMarker.next;
		for( int i = 0; i < this.size(); i++ )
			if (p.data.equals(item))
				return true;
			else
				p = p.next;
		return false;
	}

	// Adds x to the end of the list
	public boolean add( E x ) {
		add( size(), x );
		return true;
	}

	// Adds x to the list at an specific position
	// it throws an exception if the position idx does not exist
	public boolean add( int idx, E x ){
		addBefore( getNode( idx, 0, size() ), x );
		return true;
	}

	// Returns the item that is in the given position
	// it throws an exception if the position idx does not exist
	public E get( int idx ){
		return getNode( idx ).data;
	}

	// Changes the item at the position idx.
	// The new item at this position is newVal	
	public E set( int idx, E newVal )	{
		Node<E> p = getNode( idx );
		E oldVal = p.data;
		p.data = newVal;
		return oldVal;
	}

	// Removes the item at position idx. 
	// it throws an exception if the position idx does not exist
	public E remove( int idx ){
		return remove( getNode( idx ) );
	}

	// Adds x before the node p
	/**
	 * Adds an item to this collection, at specified position p.
	 * Items at or after that position are slid one position higher.
	 * @param p Node to add before.
	 * @param x any object.
	 * @throws IndexOutOfBoundsException if idx is not between 0 and size(),.
	 */
	private void addBefore( Node<E> p, E x ) {
		Node<E> newNode = new Node<E>( x, p.prev, p );
		newNode.prev.next = newNode;
		p.prev = newNode;
		theSize++;
	}

	// Removes node p
	/**
	 * Removes the object contained in Node p.
	 * @param p the Node containing the object.
	 * @return the item was removed from the collection.
	 */
	private E remove( Node<E> p )
	{
		p.next.prev = p.prev;
		p.prev.next = p.next;
		theSize--;
		//		modCount++;
		return p.data;
	}

	// Returns the node that holds the item at position idx
	// it throws an exception if the position idx does not exist
	/**
	 * Gets the Node at position idx, which must range from 0 to size( ) - 1.
	 * @param idx index to search at.
	 * @return internal node corresponding to idx.
	 * @throws IndexOutOfBoundsException if idx is not
	 * between 0 and size( ) - 1, inclusive.
	 */
	private Node<E> getNode( int idx )
	{
		return getNode( idx, 0, size( ) - 1 );
	}

	/**
	 * Gets the Node at position idx, which must range from lower to upper.
	 * @param idx index to search at.
	 * @param lower lowest valid index.
	 * @param upper highest valid index.
	 * @return internal node corresponding to idx.
	 * @throws IndexOutOfBoundsException if idx is not
	 * between lower and upper, inclusive.
	 */
	private Node<E> getNode( int idx, int lower, int upper ) {
		Node<E> p;
		if( idx < lower || idx > upper )
			throw new IndexOutOfBoundsException( );

		if( idx < size() / 2 ) {
			p = beginMarker.next;
			for( int i = 0; i < idx; i++ )
				p = p.next;
		}
		else {
			p = endMarker;
			for( int i = size(); i > idx; i-- )
				p = p.prev;
		}
		return p;
	}

	// Returns an iterator for this list
	public java.util.Iterator<E> iterator( ) {
		return new LinkedListIterator( );
	}

	private class LinkedListIterator implements java.util.Iterator<E> {
		/* Figure 3.32 */
		private Node<E> current = beginMarker.next;
		//		 private int expectedModCount = modCount;
		private boolean okToRemove = false;

		public boolean hasNext( ) {
			return current != endMarker;
		}

		public E next( ) {
			//		 if( modCount != expectedModCount )
			//		 throw new java.util.ConcurrentModificationException( );
			if( !hasNext( ) )
				throw new java.util.NoSuchElementException( );

			E nextItem = current.data;
			current = current.next;
			okToRemove = true;
			return nextItem;
		}

		public void remove( ) {
			//			if( modCount != expectedModCount )
			//				throw new java.util.ConcurrentModificationException( );
			if( !okToRemove )
				throw new IllegalStateException( );

			MyLinkedList.this.remove( current.prev );
			//			expectedModCount++;
			okToRemove = false;
		}
	}

	// Reverses the items in the list
	public void reverse(){
		Node<E> p, q;
		p = beginMarker.next;
		q = endMarker.prev;
		for( int i = 0; i < this.size() / 2; i++ ) {
			E temp = p.data;
			p.data = q.data;
			q.data = temp;
			p = p.next;
			q = q.prev;
		}
	}

	// Returns a new list which is identical to this: a clone
	public MyLinkedList<E> clone(){
		MyLinkedList<E> result = new MyLinkedList<E>();
		Node<E> p;
		p = beginMarker.next;
		for( int i = 0; i < this.size(); i++ ) {
			result.add(p.data);
			p = p.next;
		}
		return result;
	}

	// Concatenates this list with another list.
	public MyLinkedList<E> concat(MyLinkedList<E> anotherList){
		MyLinkedList<E> result = this.clone();
		Node<E> p;
		p = anotherList.beginMarker.next;
		for( int i = 0; i < anotherList.size(); i++ ) {
			result.add(p.data);
			p = p.next;
		}
		return result;
	}

	// Says if all the items in the list are different
	public boolean allDifferent(){
		Node<E> p, q;
		if (this.size()<2) return true;

		p = beginMarker.next;
		for( int i = 0; i < this.size()-1; i++ ) {
			q = p.next;
			for(int j = i+1; j < this.size(); j++) {
				if (p.data.equals(q.data))
					return false;
				q = q.next;
			}
			p = p.next;
		}
		return true;
	}

	// Says if another list is a sublist of this list
	public boolean isSublist(MyLinkedList<E> anotherList){
		//TODO
		return true;
	}

	// Says if another list is a suffix of this list
	public boolean isSuffix(MyLinkedList<E> suf){
		//TODO
		return true;
	}

	// Reorganizes the items according to the positions in idxs
	// For example, if the list is <a,b,c,d,e> and idxs is <4,2,1,0,3>,
	// the list is reorganized and the result is <e,c,b,a,d>
	public void reorganize(MyLinkedList<Integer> idxs){
		// TODO
	}

	// Returns an string that represents the items of the list. The format is 
	// <X1,X2,X3, ...,Xk>, where the items are separated by commas and enclosed between < and >
	@Override
	public String toString(){
		Node<E> p;
		p = beginMarker.next;
		String result = "<";
		for (int i=0; i<this.size()-1; i++){
			result += p.data.toString() + ",";
			p = p.next;
		}
		if(this.size()>0){
			result += p.data.toString();
		}
		return result + ">";
	}

	private static class Node<E> {
		public E data;
		public Node<E> prev;
		public Node<E> next;	

		public Node( E dat, Node<E> pre, Node<E> ne ) {
			data = dat;
			prev = pre;
			next = ne;
		}
	}

}
